package tencent_practice;

import structure.ListNode;
import structure.TreeNode;

import java.util.*;

/**
 * 二叉搜索树中第K小的元素
 */
public class Tencent_230_kthSmallest {
    List<Integer> list = new ArrayList<>();
    public int kthSmallest(TreeNode root, int k) {
        dfs(root);
        Collections.sort(list);
        return list.get(k - 1);
    }

    void dfs(TreeNode root) {
        if (root == null) {
            return;
        }
        list.add(root.val);
        dfs(root.left);
        dfs(root.right);
    }

    /**
     * 树的中序遍历
     * 迭代的方式
     */
    public int kthSmallest(TreeNode root, int k, boolean noUse) {
        Deque<TreeNode> queue = new LinkedList<>();
        while (root != null || !queue.isEmpty()) {
            while (root != null){
                queue.addLast(root);
                root = root.left;
            }
            root = queue.pollLast();
            if (--k == 0) {
                return root.val;
            }
            root = root.right;
        }
        // 表示没找到
        return -1;
    }

    /**
     * 树的中序遍历
     * 使用递归
     */
    int k, ans;
    public int kthSmallest (TreeNode root, int _k, int noUse) {
        k = _k;
        dfs(root, false);
        return ans;
    }

    void dfs(TreeNode root, boolean noUse) {
        if (root == null || k <= 0) {
            return;
        }
        dfs(root.left, noUse);
        if (--k == 0) {
            ans = root.val;
        }
        dfs(root.right, noUse);
    }

}
